package com.yc.algorithm;

import java.util.Arrays;

/**
 * @author samuel chen
 * @date 2021/6/6 10:46 下午
 **/
public class Dp {

    /**
     * simple
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 示例:
     * 输入：[-2,1,-3,4,-1,2,1,-5,4], 输出：6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     **/
    public static int maxSubArray(int[] arr) {
        // 定义数组
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int result = arr[0];
        for (int i = 1; i < dp.length; i++) {
            // 分离指标函数，列出状态转移方程
            dp[i] = Math.max(dp[i-1], 0) + arr[i];
            // 最优解是最优子结构中的最大值
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        Arrays.asList(Dp.maxSubArray(arr)).forEach(System.out::println);
    }
}
